class Solution {
public:
    string addBinary(string a, string b) {
        int carry = 0;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        int n = max(a.size(), b.size());
        string ans;
        for(size_t i = 0; i < n; ++i)
        {
            carry += i < a.size() ? a[i] == '1' : 0;
            carry += i < b.size() ? b[i] == '1' : 0;
            ans += (carry % 2) ? "1" : "0";
            carry /= 2;
        }
        if(carry) ans += "1";
        reverse(ans.begin(), ans.end());
        return ans;
    }
};
